package com.shuang.dp5;

class Solution {
    //与不同路径区别是多了障碍物
    //只需要在dp数组做文章即可  当该位置(i,j)是障碍物时dp[i][j]赋值是0 即可
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //dp[i][j] 表示从开始位置到ij位置时的不同路径数
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];

        //递归公式还是dp[i][j] = dp[i][j-1] + dp[i-1][j];但是当obstacleGrid[i][j] = 1时（当前位置是障碍物）dp[i][j] = 0

        //初始化dp数组 注意如果第一行或者第一列中的位置有障碍物挡着 那么障碍物位置和其后面的位置都应初始化为0
        //第一行
        for (int i = 0; i < obstacleGrid[0].length; i++){
            if (obstacleGrid[0][i] == 1){
                break;
            }
            dp[0][i] = 1;
        }

        //第一列
        for (int i = 0; i < obstacleGrid.length; i++){
            if (obstacleGrid[i][0] == 1){
                break;
            }
            dp[i][0] = 1;
        }

        //遍历 从左到右 上到下
        for (int i = 1; i < obstacleGrid.length; i++){
            for (int j = 1; j < obstacleGrid[0].length; j++){
                if (obstacleGrid[i][j] == 1){
                    //此位置是障碍物
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }

        return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}